package targetToOffer.thrDay;

/**
 * @author Godc
 * @description
 */
public class MinArray {
    public static void main(String[] args) {
        MinArraySolution s = new MinArraySolution();
        int[] nums = {3, 1,3};
        int i = s.minArray(nums);

    }
}
class MinArraySolution {
    /**
     * 核心还是二分
     * 首先整个数组分为两个有序部分，相当于要找到两个有序部分的边界，边界左侧是最大元素，边界右侧是最小元素
     * 将数组最后一个元素x和mid相比，如果x>mid，说明mid一定在第一个有序部分，所以边界在mid右侧
     * 如果x<mid，mid一定在第二个有序部分，边界在mid左侧
     * 以为二分
     * @param numbers
     * @return
     */
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length-1;
        while(left<right){
            int mid = (right-left)/2+left;
            // min在mid左侧
            if(numbers[mid]<numbers[right]){
                right = mid;
            }
            // 在左递增序列，分界在右侧，可以排除left不是min
            else if(numbers[mid]>numbers[right]){
                left = mid + 1;
            }
            // 因为可能会有重复数字，比较可能相等
            else
                right--;
        }
        return numbers[left];
    }
}